#include <iostream>
#include "generateAndReadData.h"

//#define GENERATE_DATA
extern double maxValue;

int main() {
#ifdef GENERATE_DATA
    /* 生成测试数据 */
    string filename = "knapsack_data.csv";
    int numItems = 20;      // 物品数量
    int maxWeight = 20;     // 物品最大重量
    int Capacity = 100;    // 背包最大容量
    //可以修改上面这些参数
    generateAndSaveData(filename, numItems, maxWeight, Capacity);
#endif


    /* 读取数据， 存放在items中 */
    vector<Item> items;
    double capacity;    // 背包容量
    readData("knapsack_data.csv", capacity, items);
    items.push_back({-1, 1, 10000});  // 使用push_back添加哨兵元素

    cout << "capacity: " << capacity << endl;


    /* it迭代器 */
    auto it = items.begin();

    int itCount = 1;
    while(it -> id != -1){
        cout << " item"  << itCount
             << " id"    << it -> id
             << " value" << it -> value
             << " weight"<< it -> weight
             << endl;
        itCount++;
        it = next(it);
    }

//    quickSortByRatio(items, 1, items.size());


//    itCount = 1;
//    it = items.begin();
//    while(it -> id != -1){
//        cout << " item"  << itCount
//             << " id"    << it -> id
//             << " value" << it -> value
//             << " weight"<< it -> weight
//             << endl;
//        itCount++;
//        it = next(it);
//    }

    cout << "=====================================================" << endl;
    cout << "=====================================================" << endl;


    /* 回溯算法 */
    maxValue = 0;  // 重置maxValue
    it = items.begin();  // 重新设置迭代器到开始位置

    auto start_backtrack = chrono::steady_clock::now();
    knapsack01_backtrack(capacity, it, 0);
    auto end_backtrack = chrono::steady_clock::now();
    auto duration_backtrack = chrono::duration_cast<chrono::microseconds>(end_backtrack - start_backtrack);

    cout << "maxValue_backtrack: " << maxValue << endl;
    cout << "backtrack time: " << duration_backtrack.count() << " microseconds" << endl;

    cout << "=====================================================" << endl;



    /* 基于循环的DP */
    it = items.begin();
    double maxValue_loop = 0;

    auto start_loop = chrono::steady_clock::now();
    maxValue_loop = knapsack01_DP_loop(int(capacity), items);
    auto end_loop = chrono::steady_clock::now();
    auto duration_loop = chrono::duration_cast<chrono::microseconds>(end_loop - start_loop);

    cout << "maxValue_loop: " << maxValue_loop << endl;
    cout << "loop time: " << duration_loop.count() << " microseconds" << endl;

    cout << "=====================================================" << endl;



    /* 基于递归的DP */
    it = items.begin();
    double maxValue_recursion = 0;

    auto start_recursion = chrono::steady_clock::now();
    maxValue_recursion = knapsack01_DP_recursion(capacity, it);
    auto end_recursion = chrono::steady_clock::now();
    auto duration_recursion = chrono::duration_cast<chrono::microseconds>(end_recursion - start_recursion);

    cout << "maxValue_recursion: " << maxValue_recursion << endl;
    cout << "recursion time: " << duration_recursion.count() << " microseconds" << endl;

    cout << "=====================================================" << endl;



    /* 贪心 */
    it = items.begin();
    double maxValue_greedy = 0;

    auto start_greedy = chrono::steady_clock::now();
    maxValue_greedy = knapsack01_greedy(capacity, it, items);
    auto end_greedy = chrono::steady_clock::now();
    auto duration_greedy = chrono::duration_cast<chrono::microseconds>(end_greedy - start_greedy);


    cout << "maxValue_greedy: " << maxValue_greedy << endl;
    cout << "greedy time: " << duration_greedy.count() << " microseconds" << endl;

    return 0;
}
